package com.huawei.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Code49 {
    public static void main(String[] args) {
        Code49 code = new Code49();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        code.groupAnagrams(strs);

    }
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
    public List<List<String>> groupAnagrams3(String[] strs) {
        List<List<String>> ans = new ArrayList<>();

        String[] strs_sort = new String[strs.length];
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            strs_sort[i] = new String(chars);
        }
        Map<String,List<Integer>> map = new HashMap<>();
        for (int i = 0; i < strs_sort.length; i++) {
            List<Integer> list = null;
            if(map.containsKey(strs_sort[i])){
                List<Integer> li = map.get(strs_sort[i]);
                li.add(i);
                map.put(strs_sort[i],li);
            }else {
                list = new ArrayList<>();
                list.add(i);
                map.put(strs_sort[i],list);
            }
        }

        Iterator<Map.Entry<String, List<Integer>>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()){
            List<Integer> value = iterator.next().getValue();
            List<String> each = new ArrayList<>();

            for (Integer i : value) {
                each.add(strs[i]);
            }
            ans.add(each);
        }

        return ans;
    }
    public List<List<String>> groupAnagrams2(String[] strs) {
        List<List<String>> ans = new ArrayList<>();

        String[] strs_sort = new String[strs.length];
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            strs_sort[i] = new String(chars);
        }

        for (int i = 0; i < strs_sort.length; i++) {
            if (strs_sort[i] == null) {
                continue;
            }
            List<String> list = new ArrayList<>();
            list.add(strs[i]);
            if (i + 1 < strs_sort.length) {
                for (int j = i + 1; j < strs_sort.length; j++) {
                    if (strs_sort[j] == null) {
                        continue;
                    }
                    if (strs_sort[i].equals(strs_sort[j])) {
                        list.add(strs[j]);
                        strs_sort[j] = null;
                    }

                }
            }
            ans.add(list);
        }
        return ans;
    }
}
